package com.example.lib5.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("结果为："+5/6+4);//优先级：*/ > () > +-
//        int[] arr = {8, 9, 1, 7};
//        int[] arr=new int[160000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i]= (int) (Math.random()*160000);
//        }
//        Date date = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String time1 = simpleDateFormat.format(date);
//        System.out.println("排序前时间："+time1);
//        shellSort(arr);//你不行啊
        shellSort3(arr);//ok
        System.out.println(Arrays.toString(arr));
//        Date date2 = new Date();
//        String time2 = simpleDateFormat.format(date2);
//        System.out.println("排序后时间："+time2);

    }

    private static void shellSort(int[] arr) {
        //第一轮
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }

                }
            }

        }
    }

    public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                //交换位置，获取这个交换的下表，然后进行交换
                if (arr[j - gap] > arr[j]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //表明找到插入位置，并插入
                    arr[j] = temp;
                }
            }
        }
    }

    //8, 9, 1, 7, 2, 3, 5, 4, 6, 0
    public static void shellSort3(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;//表示插入的那个值
                int temp = arr[j];//表示插入的那个值
                //第一个插入的值为0，数组值之间的间隔是gap
                //如果插入的时候，插入的那个值小于左边的就要找，插入点，没有泽直接插入到末尾，即无需变位置
                if (arr[j - gap] > arr[j]) {//左边的有序值大于右边的无无序值，就要找插入
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }

    }
}
